#include<string>
#include<vector>
#include<array>
#include<unordered_map>
#include<algorithm>
#include<limits>
class Solution {
public:
    int firstMissingPositive(std::vector<int>& nums) {
        int n = nums.size();
        int l = 0,r = n;
        while(l<r)
        {
            if (nums[l] == l+1)
            {
                l++;
                continue;
            }
            if (nums[l] <=l||nums[l] > r||nums[nums[l]-1] == nums[l])
            {
                r--;
                swap(nums[l],nums[r]);
                
                continue;
            }
            swap(nums[l],nums[nums[l]-1]);
        }
        return l+1;
    }
    void swap(int &a,int &b)
    {
        int temp=a;
        a=b;
        b=temp;
    }
};